/**
输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1
*/

class Solution
{
public:
  TreeNode *invertTree(TreeNode *root)
  {
    /**
     * 1、借助【队列】一层一层的遍历，然后交换 left 与 right 节点
     * 2、swap(root->left, roo->right) 交换【出队】节点
     * 3、queue.push(root->left)
     * 4、queue.push(root->right)
     */

    // 1. 创建 队列
    queue<TreeNode *> q;

    // 2. 入队 root 节点
    if (root != nullptr)
      q.push(root);

    // 3. 循环 + swap(出队节点->left, 出队节点->right)
    while (!q.empty())
    {
      // 3.1 出队节点
      TreeNode *tr = q.front();
      q.pop();

      // 3.2【交换】出队节点的 左 和 右
      swap(tr->left, tr->right);

      // 3.3 压栈 left
      if (tr->left)
        q.push(tr->left);

      // 3.4 压栈 right
      if (tr->right)
        q.push(tr->right);
    }

    return root;
  }
}
